package 程序员面试金典;

import java.util.Stack;

/**
 * 面试题 02.06. 回文链表
 * 编写一个函数，检查输入的链表是否是回文的。
 *
 *
 *
 * 示例 1：
 *
 * 输入： 1->2
 * 输出： false
 * 示例 2：
 *
 * 输入： 1->2->2->1
 * 输出： true
 */
public class T02_06 {
    //使用栈
    public boolean isPalindrome(ListNode head) {

        Stack<Integer> stack = new Stack<>();

        ListNode p = head;


        while (head!=null){

            stack.add(head.val);
            head = head.next;

        }

        while (p!=null){

            if (p.val!=stack.pop()){
                return false;
            }

            p = p.next;

        }



        return true;


    }

    public static void main(String[] args) {
        T02_06 t02_06 = new T02_06();
        ListNode listNode1 = new ListNode(1);
        ListNode listNode0 = new ListNode(0);
        ListNode listNode11 = new ListNode(1);
        listNode1.next = listNode0;
        listNode0.next = listNode11;

        t02_06.isPalindrome(listNode1);

    }


    //链表定义
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
